package com.ls.tree;

public class TreeSolution {

    TreeNode mostRigth(TreeNode node){
        while(node.right != null){
            node = node.right;
        }
        return node;
    }

    public void morris(TreeNode root){
        TreeNode cur = root;
        TreeNode mostRight = null;

        while(cur != null){

//            System.out.print(cur + " "); // morris序

            if(cur.left != null){
                // 寻找最右节点，即前驱节点
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                if(mostRight.right == cur){
                    System.out.print(cur + " "); // 中序遍历
                    mostRight.right = null;
                    cur = cur.right;

                }else{
                    mostRight.right = cur;
                    cur = cur.left;
//                    System.out.print(cur + " "); // 后续遍历
                }

            }else{
                System.out.print(cur + " ");  // 中序遍历
                cur = cur.right;
//                System.out.print(cur + " ");  // 后续遍历
            }
        }
    }

    public static void main(String[] args) {
        TreeNode head, node;
        node = head = new TreeNode(1);
        node = node.left = new TreeNode(2);
        node = node.right = new TreeNode(3);
        node = node.right = new TreeNode(7);

        TreeSolution s = new TreeSolution();
        s.morris(head);

    }
}
